<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
               "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"
lang="utf-8" xml:lang="utf-8">
<head>
<title>Lab 4: Elaboration(Type Checker)</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
<meta name="generator" content="Org-mode"/>
<meta name="generated" content="2010-06-22 18:46:18 "/>
<meta name="author" content="Zhuang Zhong"/>
<meta name="description" content=""/>
<meta name="keywords" content=""/>
<link rel="stylesheet" href="style/base.css"  type="text/css" />
<script type="text/javascript">
<!--/*--><![CDATA[/*><!--*/
 function CodeHighlightOn(elem, id)
 {
   var target = document.getElementById(id);
   if(null != target) {
     elem.cacheClassElem = elem.className;
     elem.cacheClassTarget = target.className;
     target.className = "code-highlighted";
     elem.className   = "code-highlighted";
   }
 }
 function CodeHighlightOff(elem, id)
 {
   var target = document.getElementById(id);
   if(elem.cacheClassElem)
     elem.className = elem.cacheClassElem;
   if(elem.cacheClassTarget)
     target.className = elem.cacheClassTarget;
 }
/*]]>*///-->
</script>
</head>
<body>
<div id="content">

<h1 class="title">Lab 4: Elaboration(Type Checker)</h1>



<div id="outline-container-1" class="outline-2">
<h2 id="sec-1">Introduction </h2>
<div class="outline-text-2" id="text-1">

<p>Lab 4 requires you to build AST of source code and write a type checker. In <a href="lab3.html">Lab3</a> , we have already written a "front end" for our C
language, however, we can only check whether the source code is according to the grammar. Basically, you need to:
</p><ol>
<li>
design "AST" according to the grammar
</li>
<li>
generate AST from source code
</li>
<li>
type checking on AST
<ol>
<li>
symbol table
</li>
<li>
type checker
</li>
</ol>
</li>
</ol>



</div>

</div>

<div id="outline-container-2" class="outline-2">
<h2 id="sec-2">Requirement </h2>
<div class="outline-text-2" id="text-2">


<p>
<a href="lab4.zip">Download</a> Lab4
</p>

</div>

<div id="outline-container-2.1" class="outline-3">
<h3 id="sec-2.1">Input </h3>
<div class="outline-text-3" id="text-2.1">

<p>Input of Lab4 are C files without errors on grammar. 
</p>
</div>

</div>

<div id="outline-container-2.2" class="outline-3">
<h3 id="sec-2.2">Output </h3>
<div class="outline-text-3" id="text-2.2">

<p>A sequence of all the type errors. See <a href="#sec-4">Errors</a> for more details.
</p>
</div>

</div>

<div id="outline-container-2.3" class="outline-3">
<h3 id="sec-2.3">Example </h3>
<div class="outline-text-3" id="text-2.3">




<pre class="src src-c"><span style="color: #228b22;">int</span> <span style="color: #0000ff;">add</span>(<span style="color: #228b22;">int</span> <span style="color: #b8860b;">x</span>,<span style="color: #228b22;">int</span> <span style="color: #b8860b;">y</span>);
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">listnode</span> * <span style="color: #0000ff;">malloc</span>(<span style="color: #228b22;">int</span> <span style="color: #b8860b;">size</span>);
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">listnode</span>
{
<span style="color: #228b22;">int</span> <span style="color: #b8860b;">value</span>;
<span style="color: #a020f0;">struct</span> <span style="color: #228b22;">listnode</span> * <span style="color: #b8860b;">next</span>;
}
<span style="color: #228b22;">int</span> <span style="color: #0000ff;">main</span>()
{
  <span style="color: #228b22;">int</span> <span style="color: #b8860b;">x</span>;
  <span style="color: #228b22;">int</span> <span style="color: #b8860b;">y</span>;
  <span style="color: #228b22;">int</span> <span style="color: #b8860b;">z</span>;
  <span style="color: #a020f0;">struct</span> <span style="color: #228b22;">listnode</span> * <span style="color: #b8860b;">head</span>;
  x=1;
  y=<span style="color: #bc8f8f;">"2"</span>+w; <span style="color: #b22222;">// </span><span style="color: #b22222;">typemismatch and undeclare
</span>  z=x+add(y); <span style="color: #b22222;">//</span><span style="color: #b22222;">argumentfail
</span>  head=malloc(8);
  head-&gt;value=add(x,y);
  head-&gt;next = <span style="color: #5f9ea0;">NULL</span>;
  head.value=2; <span style="color: #b22222;">// </span><span style="color: #b22222;">lvalfail
</span>  <span style="color: #a020f0;">return</span> head;  <span style="color: #b22222;">// </span><span style="color: #b22222;">returnfail   
</span>}
</pre>




<p>
The output should be:
</p>
<p>
TypeMismatch 
</p>
<p>
Undeclared
</p>
<p>
ArgumentFail
</p>
<p>
LvalFail
</p>
<p>
ReturnFail
</p>
</div>
</div>

</div>

<div id="outline-container-3" class="outline-2">
<h2 id="sec-3">Instruction </h2>
<div class="outline-text-2" id="text-3">

<dl>
<dt>To Run Lab 4</dt><dd>

<ol>
<li>
Download this package and extract
</li>
<li>
In command-line, enter the path and run:
</li>
<li>
mlyacc c.grm
</li>
<li>
mllex c.lex
</li>
<li>
MLton: mlton lab4.mlb and Run "lab4 test.c"
</li>
<li>
SML/NJ: sml sources.cm and Run lab3 like Main.parse_file "test.c".
</li>
</ol>
</dd>
<dt>File Description</dt><dd>

<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption></caption>
<colgroup><col align="left" /><col align="left" /><col align="left" />
</colgroup>
<thead>
<tr><th scope="col">Name</th><th scope="col">Description</th><th scope="col">Note</th></tr>
</thead>
<tbody>
<tr><td>c.lex</td><td>ml-lex file</td><td><b>Reuse "c.lex" from your Lab3</b></td></tr>
<tr><td>c.grm</td><td>ml-yacc file</td><td><b>Add semantic rules of Lab3</b></td></tr>
<tr><td>ast.sml</td><td>AST</td><td>Use this or write your own</td></tr>
<tr><td>typechecker.sml</td><td>Type Checker</td><td><b>Finish this file!</b></td></tr>
<tr><td>error.sml</td><td>Error Messages</td><td>Don't need to modify all the files below</td></tr>
<tr><td>symtab.sml</td><td>Symbol Table</td><td></td></tr>
<tr><td>symtab_example.sml</td><td>Example of using Symbol Table</td><td></td></tr>
<tr><td>main.sml</td><td></td><td></td></tr>
<tr><td>call-main.sml</td><td></td><td></td></tr>
<tr><td>sources.cm</td><td></td><td></td></tr>
<tr><td>lab4.mlb</td><td></td><td></td></tr>
<tr><td>test.c</td><td></td><td></td></tr>
<tr><td>License</td><td></td><td></td></tr>
</tbody>
</table>

</dd>
<dt>To Do Lab4</dt><dd>

<ol>
<li>
Finish Lab3, or you can refer to these examples of Lab3 from <b>SA09225271</b> and <b>SA09225479</b>
</li>
<li>
Take a look at "ast.sml". You can use this or write your OWN "ast.sml". 
If you are using your own AST, you may need to modify "main.sml" (see comments in main.sml) 
</li>
<li>
Read Yacc <a href="http://www.smlnj.org/doc/ML-Yacc/index.html">manual</a>, see <a href="http://www.smlnj.org/doc/ML-Yacc/mlyacc002.html#toc11">Rule</a> and <a href="http://www.smlnj.org/doc/ML-Yacc/mlyacc007.html#toc14">Sample</a> to learn how to write semantic rules.
</li>
<li>
Take a look at "symtab<sub>example</sub>.sml", try to use the symbol table
</li>
<li>
The most important is "typechecker.sml", we have given a skelton checker, 
you need to finish this. Before you start, 
take a look at the beginning parts of this file, you may need 
to use functions defined here.
</li>
</ol>
</dd>
</dl>


</div>

</div>

<div id="outline-container-4" class="outline-2">
<h2 id="sec-4"><b>Errors</b> </h2>
<div class="outline-text-2" id="text-4">

<dl>
<dt><b>TypeMismatch</b></dt><dd>

<p>
check type errors on expressions. 
</p></dd>
</dl>


<dl>
<dt><b>Undeclare</b></dt><dd>

<p>
use a variable, struct or call a function without declaration
</p></dd>
</dl>


<dl>
<dt><b>ArgumentFail</b></dt><dd>

<p>
when calling a function, check numbers of arguments or types of arguments 
</p></dd>
</dl>





<pre class="src src-c"><span style="color: #228b22;">int</span> <span style="color: #0000ff;">add</span>(<span style="color: #228b22;">int</span> <span style="color: #b8860b;">x</span>,<span style="color: #228b22;">int</span> <span style="color: #b8860b;">y</span>);
<span style="color: #228b22;">int</span> <span style="color: #b8860b;">a</span>;
<span style="color: #228b22;">int</span> <span style="color: #b8860b;">b</span>;
<span style="color: #228b22;">char</span> <span style="color: #b8860b;">c</span>;
add(a);
add(a,c);
add(a,b,c);
</pre>




<dl>
<dt><b>ReturnFail</b></dt><dd>

<p>
check the "return" statement. "ReturnFail" is the type of the return expression mismatch with declaration of the function
</p></dd>
</dl>





<pre class="src src-c"><span style="color: #228b22;">int</span> <span style="color: #0000ff;">fun</span>(<span style="color: #228b22;">int</span> <span style="color: #b8860b;">x</span>)
{
  <span style="color: #a020f0;">return</span> <span style="color: #bc8f8f;">"a"</span>;
}
</pre>




<dl>
<dt><b>LvalFail</b></dt><dd>

<p>
check statement of assignments. "LvalFail" is the type of Lval mismatch the type of right-hand side expression
</p></dd>
</dl>





<pre class="src src-c"><span style="color: #228b22;">int</span> <span style="color: #b8860b;">x</span>;
<span style="color: #228b22;">char</span> <span style="color: #b8860b;">y</span>[5];
<span style="color: #228b22;">char</span> <span style="color: #0000ff;">fun</span>();
x=<span style="color: #bc8f8f;">"a"</span>;
y[0]=1;
x=fun();
</pre>




</div>
</div>
<div id="postamble">
</div>
</div>
</body>
</html>
